# 98. 包子凑数
# https://www.lanqiao.cn/problems/?first_category_id=1&page=1&second_category_id=3
# Date: 2025/1/8
import math
from functools import reduce


def resolution(nums: list[int]):
    """
    使用动态规划的方法, 本题的重点在于如何判断INF的情况, 并且计算最大公约数.
    但是我折腾的地方在于如何定义一个i的上界, 也就是说当大于i之后的所有数字都必定可以由nums凑出, 但是实际上只要确定一个足够大的数字就行了
    """
    gcd = reduce(math.gcd, nums)  # 最大公约数
    if gcd != 1:  # 如果最大公约数不为1 则不能凑出的数量必定有无限个
        return -1
    nums.sort()
    n = 10000
    dp = [False] * n  # dp[i] 表示i能否凑出
    dp[0] = True  # 单独设置0, 方便后面dp的判断
    maxi = 0
    for i in range(1, n):
        for j in range(len(nums)):
            dp[i] |= dp[i - nums[j]]
        if not dp[i]:
            maxi = i
    print(f"max sum:{maxi}")
    return dp.count(False)


if __name__ == "__main__":
    # n = int(input())
    # nums = []
    # for i in range(n):
    #     nums.append(int(input()))
    nums = [4, 5]

    res = resolution(nums)
    print(f"result: {'INF' if res == -1 else res}")
